#define _CRT_SECURE_NO_WARNINGS 1
typedef struct Stack
{
    char* s;
    int top;
    int capacity;
}Stack;

void StackInit(Stack* ps)
{
    ps->a = (char*)malloc(sizeof(char) * 4);
    ps->top = 0;
    ps->capacity = 4;
}

void StackPush(Stack* ps, char ch)
{
    if (ps->top == ps->capacity)
    {
        int newcapacity = 2 * ps->capacity;
        char* temp = realloc(ps->a, sizeof(char) * newcapacity);
        if (temp == NULL)
        {
            printf("realloc fail\n");
            exit(-1);
        }
        else {
            ps->capacity = newcapacity;
            ps->a = temp;
        }
    }
    ps->a[ps->top] = ch;
    ps->top++;
}

void StackIsEmpty(Stack* ps)
{
    return ps->top == 0;
}

void StackPop(Stack* ps)
{
    ps->top--;
}

char StackTop(Stack* ps)
{
    return ps->a[ps->top - 1];
}

void StackDestory(Stack* ps)
{
    free(ps->a);
    ps->top = ps->capacity = 0;

}

bool isValid(char* s) {
    Stack ST;
    while (*s)
    {

        if (*s == '(' || *s == '{' || *s == '[')
        {
            StackPush(&ST, *s);
            s++;
        }
        else
        {
            if (StackIsEmpty(&ST))
            {
                StackDestory(&ST);
                return false;
            }
            else
            {
                char str = StackTop(&ST);
                if (str == '(' && ch != ')' ||
                    str == '[' && ch != ']' ||
                    str == '{' && ch != '}'
                    )
                {
                    StackDestory(&ST);
                    return false;
                }
                else {
                    ;
                }
            }
        }
    }

    return StackIsEmpty(&ST);
}